package com.ctrip.study.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 树的中序遍历.
 */
public class PreorderTraversal {

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	
	public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> datas = new ArrayList<Integer>();
        datas = inorder(datas, root);
        return datas;
    }


	private List<Integer> inorder(List<Integer> datas, TreeNode root) {
		if(root == null){
			return datas;
		}
		datas.add(root.val);
		datas = inorder(datas, root.left);
		datas = inorder(datas, root.right);
		return datas;
	}
	
}
